/*
 * @lc app=leetcode.cn id=427 lang=cpp
 * @lcpr version=30204
 *
 * [427] 建立四叉树
 */


// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
/*
// Definition for a QuadTree node.
class Node {
public:
    bool val;
    bool isLeaf;
    Node* topLeft;
    Node* topRight;
    Node* bottomLeft;
    Node* bottomRight;
    
    Node() {
        val = false;
        isLeaf = false;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }
    
    Node(bool _val, bool _isLeaf) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }
    
    Node(bool _val, bool _isLeaf, Node* _topLeft, Node* _topRight, Node* _bottomLeft, Node* _bottomRight) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = _topLeft;
        topRight = _topRight;
        bottomLeft = _bottomLeft;
        bottomRight = _bottomRight;
    }
};
*/

class Solution {
public:
    Node* construct(vector<vector<int>>& grid) {
        int n = grid.size();
        if (n == 0) return nullptr;
        return build(grid, 0, 0, n);
    }

private:
    // 检查从(row, col)开始，边长为len的正方形区域是否所有元素都相同
    bool isUniform(vector<vector<int>>& grid, int row, int col, int len) {
        int val = grid[row][col];
        for (int i = row; i < row + len; ++i) {
            for (int j = col; j < col + len; ++j) {
                if (grid[i][j] != val) {
                    return false;
                }
            }
        }
        return true;
    }
    
    // 递归构建四叉树
    Node* build(vector<vector<int>>& grid, int row, int col, int len) {
        // 如果当前区域是均质的，创建叶子节点
        if (isUniform(grid, row, col, len)) {
            return new Node(grid[row][col] == 1, true);
        }
        
        // 否则，创建非叶子节点，并递归构建四个子节点
        int half = len / 2;
        Node* topLeft = build(grid, row, col, half);
        Node* topRight = build(grid, row, col + half, half);
        Node* bottomLeft = build(grid, row + half, col, half);
        Node* bottomRight = build(grid, row + half, col + half, half);
        
        // 非叶子节点的值可以是任意（题目中未明确要求，这里用true）
        return new Node(true, false, topLeft, topRight, bottomLeft, bottomRight);
    }
};
// @lc code=end



/*
// @lcpr case=start
// [[0,1],[1,0]]\n
// @lcpr case=end

// @lcpr case=start
// [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]\n
// @lcpr case=end

 */

